동적 배열
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.
1. 개요
동적 배열은 배열과 유사하게 요소에 순차적으로 접근할 수 있으며, 필요에 따라 크기를 동적으로 조절할 수 있는 자료 구조이다. 배열의 장점을 유지하면서도, 요소의 추가 및 삭제 연산을 효율적으로 처리할 수 있도록 설계되었다. 동적 배열은 크기 조정에 따른 성능 저하를 상쇄하기 위해, 일반적으로 공간을 미리 확보하는 방식으로 구현되며, 다양한 프로그래밍 언어에서 지원된다.
더 읽어볼만한 페이지
- 분할 상환 자료 구조 - 스플레이 트리
스플레이 트리는 스플레이 연산을 통해 자가 균형을 유지하며 최근 접근 노드의 빠른 접근을 가능하게 하는 이진 탐색 트리로, 분할 상환 분석 시 평균적으로 O(log n)의 시간 복잡도를 가진다. - 분할 상환 자료 구조 - 피보나치 힙
피보나치 힙은 최소 힙 속성을 가진 트리들의 집합으로, 각 노드의 차수를 특정 로그 값 이하로 유지하여 효율적인 삽입, 병합, 최소값 검색 연산을 지원하며, 다익스트라 알고리즘과 같은 그래프 알고리즘의 성능 향상에 활용된다. - 배열 - 원형 버퍼
원형 버퍼는 고정 크기의 자료구조로, 처음과 끝이 연결되어 데이터가 순환하며 저장되는 FIFO 방식의 버퍼이며, 큐 구현, 멀티미디어 스트리밍, 데이터 압축 등에 활용된다. - 배열 - 할바흐 배열
할바흐 배열은 특정 면에 자기장을 집중시키고 다른 면에서는 상쇄시키는 배열로, 자장 격리에 유용하며 다양한 산업 및 첨단 기술 분야에 응용된다.
| 동적 배열 | |
|---|---|
| 개요 | |
| 자료 구조 유형 | 배열 |
| 접근 | Θ(1) |
| 탐색 | Θ(n) |
| 삽입 | Θ(n) |
| 삭제 | Θ(n) |
| 공간 복잡도 | Θ(n) |
| 상세 정보 | |
| 별칭 | 동적 테이블 확장 가능한 배열 동적 배열 |
| 사용 사례 | 해시 테이블 힙 |
2. 작동 원리 및 특징
동적 배열은 그 크기가 고정되지 않고, 필요에 따라 자동으로 늘어나거나 줄어드는 배열이다. 이러한 특징은 데이터의 개수를 미리 예측하기 어렵거나, 데이터가 계속 추가/삭제되는 상황에서 유용하다.
동적 배열은 내부적으로 고정 크기 배열을 사용한다. 이 고정 크기 배열에 데이터를 순차적으로 저장하며, 남는 공간은 예비 공간으로 남겨둔다. 만약 데이터를 추가하다가 예비 공간이 부족해지면, 더 큰 크기의 새로운 배열을 할당하고 기존 데이터를 복사하는 방식으로 작동한다.[2] 이 과정을 '크기 조정'이라고 하며, 일반적으로 현재 크기의 두 배로 늘리는 방식을 사용한다.
동적 배열의 끝에 요소를 추가하는 작업은 예비 공간이 충분하다면 상수 시간에 가능하다. 하지만 크기 조정이 필요한 경우에는 모든 요소를 복사해야 하므로 시간이 더 오래 걸린다. 이러한 크기 조정 비용에도 불구하고, 여러 번의 추가 작업을 고려하면 평균적으로 상수 시간에 가까운 성능을 보인다. 이를 상각 상수 시간이라고 한다.[5][6]
동적 배열은 배열과 마찬가지로 특정 위치의 요소를 빠르게 읽거나 변경할 수 있다. 또한, 요소들이 메모리에 연속적으로 저장되기 때문에 캐시 효율성이 높다는 장점도 있다. 하지만 중간에 요소를 삽입하거나 삭제하는 경우에는 뒤쪽의 요소들을 모두 이동시켜야 하므로 시간이 오래 걸린다.
다음은 동적 배열과 다른 자료 구조들의 성능을 비교한 표이다.
| rowspan=2 | | 조회 (인덱스) | 변경 (삽입 또는 삭제) | 초과 공간, 평균 | ||
|---|---|---|---|---|---|
| 시작 | 끝 | 중간 | |||
| 연결 리스트 | Θ(n) | Θ(1) | 끝 요소가 알려진 경우 Θ(1), 끝 요소가 알려지지 않은 경우 Θ(n) | Θ(n) | |
| 배열 | Θ(1) | 0 | |||
| 동적 배열 | Θ(1) | Θ(n) | Θ(1) 상각 | Θ(n)[14] | |
| 균형 트리 | Θ(log n) | Θ(log n) | Θ(log n) | Θ(n) | |
| 임의 접근 리스트 | Θ(log n)[15] | Θ(1) | Θ(n) | ||
| 해시된 배열 트리 | Θ(1) | Θ(n) | Θ(1) 상각 | Θ(√n) | |
2. 1. 용량과 크기 조정
간단한 동적 배열은 고정 크기 배열을 할당하여 구성할 수 있으며, 일반적으로 필요한 요소 수보다 크게 할당한다. 동적 배열의 요소는 기본 배열의 시작 부분에 연속적으로 저장되며, 나머지 위치는 예약되거나 사용되지 않는다. 동적 배열의 끝에 요소를 추가하는 것은 예약된 공간을 사용하여 상수 시간에 가능하다. 모든 공간이 소모된 경우, 기본 고정 크기 배열의 크기를 늘려야 한다. 일반적으로 크기 조정은 새 배열을 할당하고 원래 배열에서 각 요소를 복사해야 하므로 비용이 많이 든다. 크기 조정이 필요하지 않으므로 동적 배열의 끝에서 요소를 상수 시간에 제거할 수 있다.[2]동적 배열 내용에서 사용되는 요소의 수는 ''논리적 크기'' 또는 ''크기''이며, 기본 배열의 크기는 동적 배열의 ''용량'' 또는 ''물리적 크기''라고 하며, 이는 데이터를 재배치하지 않고 가능한 최대 크기이다.[2]
동적 배열은 크기를 두 배로 늘리는 등 큰 폭으로 크기를 조정하며, 미래 확장을 위해 예약된 공간을 사용한다. ''n''개의 요소가 삽입되면, 용량은 기하 수열을 형성한다. 배열을 임의의 상수 비율 ''a''로 확장하면 ''n''개의 요소를 삽입하는 데 전체적으로 ''O''(''n'') 시간이 걸리도록 보장하며, 이는 각 삽입이 상각 상수 시간이 걸린다는 의미이다. 많은 동적 배열은 크기가 용량의 특정 임계값, 예를 들어 30% 미만으로 떨어지면 기본 스토리지를 일부 할당 해제한다.
동적 배열의 성장 인자는 공간-시간 트레이드 오프 및 메모리 할당기 자체에 사용되는 알고리즘을 포함한 여러 요인에 따라 달라진다. 성장 인자 ''a''에 대해 삽입 연산당 평균 시간은 약 ''a''/(''a''−1)이며, 낭비되는 셀 수는 (''a''−1)''n''로 상한을 둔다. 황금비율과 1.5 값을 포함하여 이상적인 성장 인자 값에 대한 다양한 논의가 있어왔다.[4] 그러나 많은 교과서에서는 단순성과 분석 목적으로 ''a'' = 2를 사용한다.[5][6]
다음은 몇 가지 인기 있는 구현에서 사용되는 성장 인자이다.
| 구현 | 성장 인자 (a) |
|---|---|
| 자바 ArrayList[1] | 1.5 (3/2) |
| 파이썬 PyListObject[7] | ~1.125 (n + (n >> 3)) |
| 마이크로소프트 비주얼 C++ 2013[8] | 1.5 (3/2) |
| G++ 5.2.0[3] | 2 |
| Clang 3.6[3] | 2 |
| 페이스북 folly/FBVector[9] | 1.5 (3/2) |
| 러스트 Vec[10] | 2 |
| Go 슬라이스[11] | 1.25와 2 사이 |
| 님 시퀀스[12] | 2 |
| SBCL (커먼 리스프) 벡터[13] | 2 |
| C# (.NET) 8) List | 2 |
2. 2. 성장 인자 (Growth Factor)
동적 배열은 크기를 조절할 때, 일반적으로 현재 크기의 두 배로 늘리는 방식을 사용한다. 이는 잦은 크기 조정으로 인한 비용을 줄이고, 미래에 추가될 요소를 위한 공간을 확보하기 위함이다.[5][6]예를 들어, ''n''개의 요소를 동적 배열의 끝에 추가하면, 배열의 용량은 기하 수열 형태로 증가한다. 배열의 크기를 상수 비율 ''a''로 늘리면, ''n''개의 요소를 추가하는 데 걸리는 총 시간은 ''O''(''n'')이 된다. 즉, 각 요소 추가 작업은 상각 상수 시간이 걸린다.
동적 배열의 성장 인자는 공간-시간 트레이드 오프 등 여러 요인에 따라 결정된다. 성장 인자 ''a''에 대해 삽입 연산당 평균 시간은 약 ''a'' / (''a'' - 1)이며, 낭비되는 셀 수는 (''a'' - 1)''n''을 상한으로 한다. 메모리 할당 알고리즘에 따라서는 성장 인자 값 ''a'' = 2와 같은 값은 상당한 양의 메모리가 여전히 사용 가능하더라도 동적 배열 확장이 메모리 부족으로 실행될 수 있다.[3] 황금비율과 1.5 값을 포함하여 이상적인 성장 인자 값에 대한 다양한 논의가 있어왔다.[4] 그러나 많은 교과서에서는 단순성과 분석 목적으로 ''a'' = 2를 사용한다.[5][6]
몇 가지 프로그래밍 언어 및 구현체 별 성장 인자는 다음과 같다.
| 구현 | 성장 인자 (a) |
|---|---|
| 자바 ArrayList[1] | 1.5 (3/2) |
| 파이썬 PyListObject[7] | ~1.125 (n + (n >> 3)) |
| 마이크로소프트 비주얼 C++ 2013[8] | 1.5 (3/2) |
| G++ 5.2.0[3] | 2 |
| Clang 3.6[3] | 2 |
| 페이스북 folly/FBVector[9] | 1.5 (3/2) |
| 러스트 Vec[10] | 2 |
| Go 슬라이스[11] | 1.25와 2 사이 |
| 님 시퀀스[12] | 2 |
| SBCL (커먼 리스프) 벡터[13] | 2 |
| C# (.NET) 8) List | 2 |
2. 3. 성능 분석
(인덱스)평균
끝 요소가 알려지지 않은 경우 Θ(n)